package binarytree

func MaxDepth(root *TreeNode) int {
	// 递归比较左右子树即可
	// 计算深度的时候，通过参数传递上层深度进入目标层级即可
	depth := 0
	return findMaxDepth(root, depth)

}

func findMaxDepth(node *TreeNode, depth int) int {
	if node == nil {
		return depth
	}
	depth += 1
	leftDeep := findMaxDepth(node.Left, depth)
	rightDeep := findMaxDepth(node.Right, depth)
	if leftDeep > rightDeep {
		return leftDeep
	} else {
		return rightDeep
	}
}

func MinDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return findMinDepth(root, 0)
}

func findMinDepth(node *TreeNode, depth int) int {
	if node.Left == nil && node.Right == nil {
		return depth + 1
	} else if node.Left == nil {
		return findMinDepth(node.Right, depth+1)
	} else if node.Right == nil {
		return findMinDepth(node.Left, depth+1)
	} else {
		left := findMinDepth(node.Left, depth+1)
		right := findMinDepth(node.Right, depth+1)
		if left > right {
			return right
		} else {
			return left
		}
	}
}
